#include<iostream>
using namespace std;
#include<vector>



//class Solution {
//public:
//    vector<int> sortArray(vector<int>& nums) {
//        int n = nums.size(), left = -1, right = n, i = 0;
//        int key = (n - 1) / 2;
//        swap(nums[key], nums[0]);
//        int key1 = nums[0];
//        while (i < right)
//        {
//            if (nums[i] == key1)
//                i++;
//            else if (nums[i] < key1)
//                swap(nums[++left], nums[i++]);
//            else
//                swap(nums[i], nums[--right]);
//        }
//        return nums;
//
//    }
//};

class Solution {
public:
    int GetRandom(vector<int>& nums, int left, int right)
    {
        int r = rand();
        return nums[r % (right - left + 1) + left];
    }
    void qsort(vector<int>& nums, int l, int r)
    {
        if (l >= r)
            return;
        int key = GetRandom(nums, l, r);
        int i = l, left = l - 1, right = r + 1;
        while (i < right)
        {
            if (nums[i] == key)
                i++;
            else if (nums[i] < key)
                swap(nums[++left], nums[i++]);
            else
                swap(nums[i], nums[--right]);
        }
        qsort(nums, l, left);
        qsort(nums, right, r);

    }
    vector<int> sortArray(vector<int>& nums) {
        srand(time(NULL));
        qsort(nums, 0, nums.size() - 1);
        return nums;
    }

};
int main()
{
    vector<int> v = { -4,0,7,4,9,-5,-1,0,-7,-1 };
    Solution s;
    s.sortArray(v);
    return 0;
}